package week09

// 1091. 二进制矩阵中的最短路径
// https://leetcode-cn.com/problems/shortest-path-in-binary-matrix/

func shortestPathBinaryMatrix(grid [][]int) int {
	var n = len(grid)
	if grid[0][0] == 1 || grid[n-1][n-1] == 1 {
		return -1
	}
	if n == 1 {
		return 1
	}

	var distBegin = make([][]int, n)
	var distEnd = make([][]int, n)
	for i := range grid {
		distBegin[i] = make([]int, n)
		distEnd[i] = make([]int, n)
		for j := range grid[i] {
			distBegin[i][j] = 1e9
			distEnd[i][j] = 1e9
		}
	}
	distBegin[0][0], distEnd[n-1][n-1] = 1, 1
	qBegin := [][]int{{0, 0}}
	qEnd := [][]int{{n-1, n-1}}
	ans := 0
	for len(qBegin) > 0 && len(qEnd) > 0 {
		if qBegin, ans = bfs(grid, qBegin, distBegin, distEnd); ans > 0 {
			return ans
		}
		if qEnd, ans = bfs(grid, qEnd, distEnd, distBegin); ans > 0 {
			return ans
		}
	}
	return -1
}

func bfs(grid [][]int, queue [][]int, dist, other [][]int) ([][]int, int) {
	var ans int = 1e9
	pos := queue[0]
	queue = queue[1:]

	x, y := pos[0], pos[1]
	for dir := range dx {
		nx := x + dx[dir]
		ny := y + dy[dir]
		if !isValid(grid, nx, ny) {
			continue
		}
		if dist[nx][ny] != 1e9 {
			continue
		}
		if other[nx][ny] != 1e9 { // 碰上了
			ans = min(ans, dist[x][y] + other[nx][ny])
		}
		dist[nx][ny] = dist[x][y]+1
		queue = append(queue, []int{nx, ny})
	}
	if ans == 1e9 {
		ans = 0
	}
	return queue, 0
}

func isValid(grid [][]int, x, y int) bool {
	return x >= 0 && y >= 0 && x < len(grid) && y < len(grid[x]) && grid[x][y] == 0
}

func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}

var dx = []int{1, 1, -1, -1, 0, 1, 0, -1}
var dy = []int{1, -1, -1, 1, 1, 0, -1, 0}